home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / BYacc-CW 1.9 / lr0.c < prev    next >
Text File  |  1995-05-20  |  10KB  |  596 lines
  1.  
  2. #include "defs.h"
  3.  
  4. extern short *itemset;
  5. extern short *itemsetend;
  6. extern unsigned *ruleset;
  7.  
  8. int nstates;
  9. core *first_state;
  10. shifts *first_shift;
  11. reductions *first_reduction;
  12.  
  13. int get_state();
  14. core *new_state();
  15.  
  16. static core **state_set;
  17. static core *this_state;
  18. static core *last_state;
  19. static shifts *last_shift;
  20. static reductions *last_reduction;
  21.  
  22. static int nshifts;
  23. static short *shift_symbol;
  24.  
  25. static short *redset;
  26. static short *shiftset;
  27.  
  28. static short **kernel_base;
  29. static short **kernel_end;
  30. static short *kernel_items;
  31.  
  32.  
  33. static void allocate_itemsets(void)
  34. {
  35.     register short *itemp;
  36.     register short *item_end;
  37.     register int symbol;
  38.     register int i;
  39.     register int count;
  40.     register int max;
  41.     register short *symbol_count;
  42.  
  43.     count = 0;
  44.     symbol_count = NEW2(nsyms, short);
  45.  
  46.     item_end = ritem + nitems;
  47.     for (itemp = ritem; itemp < item_end; itemp++)
  48.     {
  49.     symbol = *itemp;
  50.     if (symbol >= 0)
  51.     {
  52.         count++;
  53.         symbol_count[symbol]++;
  54.     }
  55.     }
  56.  
  57.     kernel_base = NEW2(nsyms, short *);
  58.     kernel_items = NEW2(count, short);
  59.  
  60.     count = 0;
  61.     max = 0;
  62.     for (i = 0; i < nsyms; i++)
  63.     {
  64.     kernel_base[i] = kernel_items + count;
  65.     count += symbol_count[i];
  66.     if (max < symbol_count[i])
  67.         max = symbol_count[i];
  68.     }
  69.  
  70.     shift_symbol = symbol_count;
  71.     kernel_end = NEW2(nsyms, short *);
  72. }
  73.  
  74.  
  75. static void allocate_storage(void)
  76. {
  77.     allocate_itemsets();
  78.     shiftset = NEW2(nsyms, short);
  79.     redset = NEW2(nrules + 1, short);
  80.     state_set = NEW2(nitems, core *);
  81. }
  82.  
  83.  
  84. static void append_states(void)
  85. {
  86.     register int i;
  87.     register int j;
  88.     register int symbol;
  89.  
  90. #ifdef    TRACE
  91.     fprintf(stderr, "Entering append_states()\n");
  92. #endif
  93.     for (i = 1; i < nshifts; i++)
  94.     {
  95.     symbol = shift_symbol[i];
  96.     j = i;
  97.     while (j > 0 && shift_symbol[j - 1] > symbol)
  98.     {
  99.         shift_symbol[j] = shift_symbol[j - 1];
  100.         j--;
  101.     }
  102.     shift_symbol[j] = symbol;
  103.     }
  104.  
  105.     for (i = 0; i < nshifts; i++)
  106.     {
  107.     symbol = shift_symbol[i];
  108.     shiftset[i] = get_state(symbol);
  109.     }
  110. }
  111.  
  112.  
  113. static void free_storage(void)
  114. {
  115.     FREE(shift_symbol);
  116.     FREE(redset);
  117.     FREE(shiftset);
  118.     FREE(kernel_base);
  119.     FREE(kernel_end);
  120.     FREE(kernel_items);
  121.     FREE(state_set);
  122. }
  123.  
  124.  
  125.  
  126.  
  127.  
  128. static int get_state(int symbol)
  129. {
  130.     register int key;
  131.     register short *isp1;
  132.     register short *isp2;
  133.     register short *iend;
  134.     register core *sp;
  135.     register int found;
  136.     register int n;
  137.  
  138. #ifdef    TRACE
  139.     fprintf(stderr, "Entering get_state(%d)\n", symbol);
  140. #endif
  141.  
  142.     isp1 = kernel_base[symbol];
  143.     iend = kernel_end[symbol];
  144.     n = iend - isp1;
  145.  
  146.     key = *isp1;
  147.     assert(0 <= key && key < nitems);
  148.     sp = state_set[key];
  149.     if (sp)
  150.     {
  151.     found = 0;
  152.     while (!found)
  153.     {
  154.         if (sp->nitems == n)
  155.         {
  156.         found = 1;
  157.         isp1 = kernel_base[symbol];
  158.         isp2 = sp->items;
  159.  
  160.         while (found && isp1 < iend)
  161.         {
  162.             if (*isp1++ != *isp2++)
  163.             found = 0;
  164.         }
  165.         }
  166.  
  167.         if (!found)
  168.         {
  169.         if (sp->link)
  170.         {
  171.             sp = sp->link;
  172.         }
  173.         else
  174.         {
  175.             sp = sp->link = new_state(symbol);
  176.             found = 1;
  177.         }
  178.         }
  179.     }
  180.     }
  181.     else
  182.     {
  183.     state_set[key] = sp = new_state(symbol);
  184.     }
  185.  
  186.     return (sp->number);
  187. }
  188.  
  189.  
  190.  
  191. static void initialize_states(void)
  192. {
  193.     register int i;
  194.     register short *start_derives;
  195.     register core *p;
  196.  
  197.     start_derives = derives[start_symbol];
  198.     for (i = 0; start_derives[i] >= 0; ++i)
  199.     continue;
  200.  
  201.     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
  202.     if (p == 0) no_space();
  203.  
  204.     p->next = 0;
  205.     p->link = 0;
  206.     p->number = 0;
  207.     p->accessing_symbol = 0;
  208.     p->nitems = i;
  209.  
  210.     for (i = 0;  start_derives[i] >= 0; ++i)
  211.     p->items[i] = rrhs[start_derives[i]];
  212.  
  213.     first_state = last_state = this_state = p;
  214.     nstates = 1;
  215. }
  216.  
  217.  
  218. static void new_itemsets(void)
  219. {
  220.     register int i;
  221.     register int shiftcount;
  222.     register short *isp;
  223.     register short *ksp;
  224.     register int symbol;
  225.  
  226.     for (i = 0; i < nsyms; i++)
  227.     kernel_end[i] = 0;
  228.  
  229.     shiftcount = 0;
  230.     isp = itemset;
  231.     while (isp < itemsetend)
  232.     {
  233.     i = *isp++;
  234.     symbol = ritem[i];
  235.     if (symbol > 0)
  236.     {
  237.         ksp = kernel_end[symbol];
  238.         if (!ksp)
  239.         {
  240.         shift_symbol[shiftcount++] = symbol;
  241.         ksp = kernel_base[symbol];
  242.         }
  243.  
  244.         *ksp++ = i + 1;
  245.         kernel_end[symbol] = ksp;
  246.     }
  247.     }
  248.  
  249.     nshifts = shiftcount;
  250. }
  251.  
  252.  
  253.  
  254. static core *new_state(int symbol)
  255. {
  256.     register int n;
  257.     register core *p;
  258.     register short *isp1;
  259.     register short *isp2;
  260.     register short *iend;
  261.  
  262. #ifdef    TRACE
  263.     fprintf(stderr, "Entering new_state(%d)\n", symbol);
  264. #endif
  265.  
  266.     if (nstates >= MAXSHORT)
  267.     fatal("too many states");
  268.  
  269.     isp1 = kernel_base[symbol];
  270.     iend = kernel_end[symbol];
  271.     n = iend - isp1;
  272.  
  273.     p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
  274.     p->accessing_symbol = symbol;
  275.     p->number = nstates;
  276.     p->nitems = n;
  277.  
  278.     isp2 = p->items;
  279.     while (isp1 < iend)
  280.     *isp2++ = *isp1++;
  281.  
  282.     last_state->next = p;
  283.     last_state = p;
  284.  
  285.     nstates++;
  286.  
  287.     return (p);
  288. }
  289.  
  290.  
  291. /* show_cores is used for debugging */
  292.  
  293. static void show_cores(void)
  294. {
  295.     core *p;
  296.     int i, j, k, n;
  297.     int itemno;
  298.  
  299.     k = 0;
  300.     for (p = first_state; p; ++k, p = p->next)
  301.     {
  302.     if (k) printf("\n");
  303.     printf("state %d, number = %d, accessing symbol = %s\n",
  304.         k, p->number, symbol_name[p->accessing_symbol]);
  305.     n = p->nitems;
  306.     for (i = 0; i < n; ++i)
  307.     {
  308.         itemno = p->items[i];
  309.         printf("%4d  ", itemno);
  310.         j = itemno;
  311.         while (ritem[j] >= 0) ++j;
  312.         printf("%s :", symbol_name[rlhs[-ritem[j]]]);
  313.         j = rrhs[-ritem[j]];
  314.         while (j < itemno)
  315.         printf(" %s", symbol_name[ritem[j++]]);
  316.         printf(" .");
  317.         while (ritem[j] >= 0)
  318.         printf(" %s", symbol_name[ritem[j++]]);
  319.         printf("\n");
  320.         fflush(stdout);
  321.     }
  322.     }
  323. }
  324.  
  325.  
  326. /* show_ritems is used for debugging */
  327.  
  328. static void show_ritems(void)
  329. {
  330.     int i;
  331.  
  332.     for (i = 0; i < nitems; ++i)
  333.     printf("ritem[%d] = %d\n", i, ritem[i]);
  334. }
  335.  
  336.  
  337. /* show_rrhs is used for debugging */
  338. static void show_rrhs(void)
  339. {
  340.     int i;
  341.  
  342.     for (i = 0; i < nrules; ++i)
  343.     printf("rrhs[%d] = %d\n", i, rrhs[i]);
  344. }
  345.  
  346.  
  347. /* show_shifts is used for debugging */
  348.  
  349. static void show_shifts(void)
  350. {
  351.     shifts *p;
  352.     int i, j, k;
  353.  
  354.     k = 0;
  355.     for (p = first_shift; p; ++k, p = p->next)
  356.     {
  357.     if (k) printf("\n");
  358.     printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
  359.         p->nshifts);
  360.     j = p->nshifts;
  361.     for (i = 0; i < j; ++i)
  362.         printf("\t%d\n", p->shift[i]);
  363.     }
  364. }
  365.  
  366.  
  367. static void save_shifts(void)
  368. {
  369.     register shifts *p;
  370.     register short *sp1;
  371.     register short *sp2;
  372.     register short *send;
  373.  
  374.     p = (shifts *) allocate((unsigned) (sizeof(shifts) +
  375.             (nshifts - 1) * sizeof(short)));
  376.  
  377.     p->number = this_state->number;
  378.     p->nshifts = nshifts;
  379.  
  380.     sp1 = shiftset;
  381.     sp2 = p->shift;
  382.     send = shiftset + nshifts;
  383.  
  384.     while (sp1 < send)
  385.     *sp2++ = *sp1++;
  386.  
  387.     if (last_shift)
  388.     {
  389.     last_shift->next = p;
  390.     last_shift = p;
  391.     }
  392.     else
  393.     {
  394.     first_shift = p;
  395.     last_shift = p;
  396.     }
  397. }
  398.  
  399.  
  400.  
  401. static void save_reductions(void)
  402. {
  403.     register short *isp;
  404.     register short *rp1;
  405.     register short *rp2;
  406.     register int item;
  407.     register int count;
  408.     register reductions *p;
  409.     register short *rend;
  410.  
  411.     count = 0;
  412.     for (isp = itemset; isp < itemsetend; isp++)
  413.     {
  414.     item = ritem[*isp];
  415.     if (item < 0)
  416.     {
  417.         redset[count++] = -item;
  418.     }
  419.     }
  420.  
  421.     if (count)
  422.     {
  423.     p = (reductions *) allocate((unsigned) (sizeof(reductions) +
  424.                     (count - 1) * sizeof(short)));
  425.  
  426.     p->number = this_state->number;
  427.     p->nreds = count;
  428.  
  429.     rp1 = redset;
  430.     rp2 = p->rules;
  431.     rend = rp1 + count;
  432.  
  433.     while (rp1 < rend)
  434.         *rp2++ = *rp1++;
  435.  
  436.     if (last_reduction)
  437.     {
  438.         last_reduction->next = p;
  439.         last_reduction = p;
  440.     }
  441.     else
  442.     {
  443.         first_reduction = p;
  444.         last_reduction = p;
  445.     }
  446.     }
  447. }
  448.  
  449.  
  450. static void set_derives(void)
  451. {
  452.     register int i, k;
  453.     register int lhs;
  454.     register short *rules;
  455.  
  456.     derives = NEW2(nsyms, short *);
  457.     rules = NEW2(nvars + nrules, short);
  458.  
  459.     k = 0;
  460.     for (lhs = start_symbol; lhs < nsyms; lhs++)
  461.     {
  462.     derives[lhs] = rules + k;
  463.     for (i = 0; i < nrules; i++)
  464.     {
  465.         if (rlhs[i] == lhs)
  466.         {
  467.         rules[k] = i;
  468.         k++;
  469.         }
  470.     }
  471.     rules[k] = -1;
  472.     k++;
  473.     }
  474.  
  475. #ifdef    DEBUG
  476.     print_derives();
  477. #endif
  478. }
  479.  
  480. static void free_derives(void)
  481. {
  482.     FREE(derives[start_symbol]);
  483.     FREE(derives);
  484. }
  485.  
  486. #ifdef    DEBUG
  487. static void print_derives(void)
  488. {
  489.     register int i;
  490.     register short *sp;
  491.  
  492.     printf("\nDERIVES\n\n");
  493.  
  494.     for (i = start_symbol; i < nsyms; i++)
  495.     {
  496.     printf("%s derives ", symbol_name[i]);
  497.     for (sp = derives[i]; *sp >= 0; sp++)
  498.     {
  499.         printf("  %d", *sp);
  500.     }
  501.     putchar('\n');
  502.     }
  503.  
  504.     putchar('\n');
  505. }
  506. #endif
  507.  
  508.  
  509. static void set_nullable(void)
  510. {
  511.     register int i, j;
  512.     register int empty;
  513.     int done;
  514.  
  515.     nullable = MALLOC(nsyms);
  516.     if (nullable == 0) no_space();
  517.  
  518.     for (i = 0; i < nsyms; ++i)
  519.     nullable[i] = 0;
  520.  
  521.     done = 0;
  522.     while (!done)
  523.     {
  524.     done = 1;
  525.     for (i = 1; i < nitems; i++)
  526.     {
  527.         empty = 1;
  528.         while ((j = ritem[i]) >= 0)
  529.         {
  530.         if (!nullable[j])
  531.             empty = 0;
  532.         ++i;
  533.         }
  534.         if (empty)
  535.         {
  536.         j = rlhs[-j];
  537.         if (!nullable[j])
  538.         {
  539.             nullable[j] = 1;
  540.             done = 0;
  541.         }
  542.         }
  543.     }
  544.     }
  545.  
  546. #ifdef DEBUG
  547.     for (i = 0; i < nsyms; i++)
  548.     {
  549.     if (nullable[i])
  550.         printf("%s is nullable\n", symbol_name[i]);
  551.     else
  552.         printf("%s is not nullable\n", symbol_name[i]);
  553.     }
  554. #endif
  555. }
  556.  
  557.  
  558. static void free_nullable(void)
  559. {
  560.     FREE(nullable);
  561. }
  562.  
  563.  
  564. static void generate_states(void)
  565. {
  566.     allocate_storage();
  567.     itemset = NEW2(nitems, short);
  568.     ruleset = NEW2(WORDSIZE(nrules), unsigned);
  569.     set_first_derives();
  570.     initialize_states();
  571.  
  572.     while (this_state)
  573.     {
  574.     closure(this_state->items, this_state->nitems);
  575.     save_reductions();
  576.     new_itemsets();
  577.     append_states();
  578.  
  579.     if (nshifts > 0)
  580.         save_shifts();
  581.  
  582.     this_state = this_state->next;
  583.     }
  584.  
  585.     finalize_closure();
  586.     free_storage();
  587. }
  588.  
  589.  
  590. void lr0(void)
  591. {
  592.     set_derives();
  593.     set_nullable();
  594.     generate_states();
  595. }
  596.